package niuke;
/**
 * NC105 二分查找-II
 *
 * 描述
 * 请实现有重复数字的升序数组的二分查找
 * 给定一个 元素有序的（升序）长度为n的整型数组 nums 和一个目标值 target  ，写一个函数搜索 nums 中的第一个出现的target，如果目标值存在返回下标，否则返回 -1
 *
 * 数据范围：
 * 进阶：时间复杂度，空间复杂度
 * 示例1
 * 输入：
 * [1,2,4,4,5],4
 * 复制
 * 返回值：
 * 2
 * 复制
 * 说明：
 * 从左到右，查找到第1个为4的，下标为2，返回2
 * 示例2
 * 输入：
 * [1,2,4,4,5],3
 * 复制
 * 返回值：
 * -1
 * 复制
 * 示例3
 * 输入：
 * [1,1,1,1,1],1
 * 复制
 * 返回值：
 * 0
 * */
public class BinarySearch {

    public static void main(String[] args) {
        int[] nums = {};
        BinarySearch binarySearch = new BinarySearch();
        System.out.println(binarySearch.search(nums, 0));
    }

    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 如果目标值存在返回下标，否则返回 -1
     * @param nums int整型一维数组
     * @param target int整型
     * @return int整型
     */
    public int search (int[] nums, int target) {
        if (nums.length == 0){
            return -1;
        }
        // write code here
        int left = 0, right = nums.length -1;
        int tem = this.BinSaerch(nums, left, right, target);
        if (tem == -1){
            return -1;
        }
        for (int i = tem-1; i > 0; i--){
            if (nums[tem] == nums[i]){
                tem = i;
            }else {
                break;
            }
        }
        return tem;
    }

    public int BinSaerch(int[] nums,int left, int right, int target){
        int middle = (left + right ) / 2;
//        int middle = left + (right - left) / 2;
        /**
         * 判断是否合法
         * */
        if (nums[left] > target){
            return -1;
        }
        if (nums[right] < target){
            return -1;
        }
        /**
         * 判断端点值
         * */
        if (nums[left] == target){
            return left;
        }
        if (nums[right] == target){
            return right;
        }
        if (nums[middle] == target){
            return middle;
        }
        /**
         *
         * */
        if (middle <= left || middle >= right){
            return -1;
        }
        if (nums[left] < target && nums[middle] > target){
            right = middle;
            return BinSaerch(nums,left,right,target);
        }
        if (nums[right] > target && nums[middle] < target){
            left = middle;
            return BinSaerch(nums,left,right,target);
        }

        return -1;
    }
}
